#include "../tools.h"
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return 1;
        
        // 末尾元素最小的最长递增子序列
        vector<int> tail;
        tail.push_back(nums[0]);

        auto pbegin = tail.begin();
        for(int i = 1; i < nums.size(); ++i){
            if(nums[i] > tail.back()) tail.push_back(nums[i]);
            else{
                auto p = upper_bound(tail.begin(), tail.end(), nums[i]);
                *p = nums[i];
            }
        }
        show(tail);
        return tail.size();
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    vector<int> nums = {7,7,7,7,7,7,7};

    int res = sol.lengthOfLIS(nums);

    cout << res << endl;

    return 0;
}
